﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<algorithm>


using namespace std;


//快乐数
class Solution {
public:

    int nextNum(int n)
    {
        int sum = 0;
        while (n)
        {
            int rem = n % 10;
            n /= 10;
            sum += rem * rem;
        }
        return sum;
    }


    bool isHappy(int n)
    {
        int slow = n;
        int fast = nextNum(n);
        while (slow != fast)
        {
            slow = nextNum(slow);
            fast = nextNum(fast);
            fast = nextNum(fast);
        }

        return slow == 1;
    }


    //盛最多水的容器
    int maxArea(vector<int>& h)
    {
        int left = 0;
        int right = h.size() - 1;
        int capacity = 0;
        while (left < right)
        {
            int length = min(h[left], h[right]);
            int tmp = (right - left) * length;
            if (h[left] < h[right])
            {
                left++;
            }
            else
            {
                right--;
            }
            capacity = max(capacity, tmp);
        }
        return capacity;
    }

    //
    int triangleNumber(vector<int>& nums)
    {
        //排序使其为递增,比一次加单调性双指针。
        sort(nums.begin(), nums.end());

        int size = nums.size();
        int count = 0;
        for (int i = size - 1; i >= 2; i--)
        {
            int left = 0;
            int right = i - 1;
            while (left < right)
            {
                if (nums[left] + nums[right] > nums[i])
                {
                    count += right - left;
                    right--;
                }
                else
                {
                    left++;
                }
            }
        }
        return count;
    }

    //查找总价格为目标值的两个商品
    vector<int> twoSum(vector<int>& price, int target)
    {
        int left = 0;
        int right = price.size() - 1;
        while (left < right)
        {
            if (price[left] + price[right] < target)
            {
                left++;
            }
            else if (price[left] + price[right] > target)
            {
                right--;
            }
            else
            {
                return { price[left],price[right] };
            }
        }
        return {};
    }

    //三数之和
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        vector<vector<int>> ret;
        // 1. 排序
        sort(nums.begin(), nums.end());
        // 2. 利⽤双指针解决问题
        int n = nums.size();
        for (int i = 0; i < n; ) // 固定数 a
        {
            if (nums[i] > 0) break; // ⼩优化
            int left = i + 1, right = n - 1, target = -nums[i];
            while (left < right)
            {
                int sum = nums[left] + nums[right];
                if (sum > target) right--;
                else if (sum < target) left++;
                else
                {
                    ret.push_back({ nums[i], nums[left], nums[right] });
                    left++, right--;
                    // 去重操作 left 和 right
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1])
                        right--;
                }
            }
            // 去重 i
            i++;
            while (i < n && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }

      vector<vector<int>> threesum(vector<int>& nums) 
     {
         vector<vector<int>> vv;
         sort(nums.begin(),nums.end());
         for(int i = 0;i < nums.size()-2;i++)
         {

             if(nums[i] > 0) break;
             int left = i+1;
             int right = nums.size()-1;
             while(left < right)
             {
                 if(nums[left] + nums[right] > -nums[i])
                 {
                     right--;
                 }
                 else if(nums[left] + nums[right] < -nums[i])
                 {
                     left++;
                 }
                 else
                 {
                     vv.push_back({nums[i],nums[left],nums[right]});
                     left++;
                     right--;
                     //处理区间里面重复的
                     while(left < right)
                     {
                         if(nums[left] != nums[left-1] && nums[right] != nums[right+1])
                         {
                             break;
                         }
                         if(nums[left] == nums[left-1])
                         {
                             left++;
                         }
                         if(nums[right] == nums[right+1])
                         {
                             right--;
                         }
                     }

                     //处理nums[i]的重复
                     while(i + 1 < nums.size()-2 && nums[i] == nums[i+1])
                     {
                         i++;
                     }
                 }
             }
         }

         return vv;
     }





};





int main()
{

	return 0;
}